A. Field of the Invention
The present invention relates to a method and device for recovering timing information in a multi-carrier communication system. Specifically the invention relates to a method and structure for correcting for the effects of a frequency offset between a transmitter clock and a receiver clock in a multi-carrier transmission system, as found, for example, in ADSL transceivers.
B. Description of the Related Art
1. Asymmetric Digital Subscriber Lines
Asymmetric Digital Subscriber Line (ADSL) is a communication system that operates over existing twisted-pair telephone lines between a central office and a residential or business location. It is generally a point-to-point connection between two dedicated devices, as opposed to multi-point, where numerous devices share the same physical medium.
ADSL supports bit transmission rates of up to approximately 6 Mbps in the downstream direction (to a subscriber device at the home), but only 640 Kbps in the upstream direction (to the service provider/central office). ADSL connections actually have three separate information channels: two data channels and a POTS channel. The first data channel is a high-speed downstream channel used to convey information to the subscriber. Its data rate is adaptable and ranges from 1.5 to 6.1 Mbps. The second data channel is a medium speed upstream channel providing bidirectional communication between the subscriber and the service provider/central office. Its rate is also adaptable and the rates range from 16 to 640 kbps. The third information channel is a POTS (Plain Old Telephone Service) channel. The POTS channel is typically not processed directly by the ADSL modemsxe2x80x94the POTS channel operates in the standard POTS frequency range and is processed by standard POTS devices after being split from the ADSL signal.
The American National Standards Institute (ANSI) Standard T1.413, the contents of which are incorporated herein by reference, specifies an ADSL standard that is widely followed in the telecommunications industry. A similar standard, Recommendation G.992.1 from the ITU, is also incorporated herein by reference. A variation of the standard that accomodates POTS service without the use of a signal splitter is set forth in specification G.Lite, or Recommendation G.992.2, the contents of which are incorporated herein by reference. The ADSL standards specify a modulation technique known as Discrete Multi-Tone modulation.
2. Discrete Multi-tone Modulation
Discrete Multi-Tone (DMT) uses a large number of subcarriers spaced close together. Each subcarrier is modulated using a type of Quadrature Amplitude Modulation (QAM). Alternative types of modulation include Multiple Phase Shift Keying (MPSK), including BPSK and QPSK, and Differential Phase Shift Keying (DPSK). The data bits are mapped to a series of symbols in the I-Q complex plane, and each symbol is used to modulate the amplitude and phase of one of the multiple tones, or carriers. The symbols are used to specify the magnitude and phase of a subcarrier, where each subcarrier frequency corresponds to the center frequency of the xe2x80x9cbinxe2x80x9d associated with a Discrete Fourier Transform (DFT). The modulated time-domain signal corresponding to all of the subcarriers can then be generated in parallel by the use of well-known DFT algorithm called Inverse Fast Fourier Transforms (IFFT).
The symbol period is relatively long compared to single carrier systems because the bandwidth available to each carrier is restricted. However, a large number of symbols is transmitted simultaneously, one on each subcarrier. The number of discrete signal points that may be distinguished on a single carrier is a function of the noise level. Thus, the signal set, or constellation, of each subcarrier is determined based on the noise level within the relevant subcarrier frequency band.
Because the symbol time is relatively long and follows a guard band, intersymbol interference is a less severe problem than with single carrier, high symbol rate systems. Furthermore, because each carrier has a narrow bandwidth, the channel impulse response is relatively flat across each subcarrier frequency band. The DMT standard for ADSL, ANSI T1.413, specifies 256 subcarriers, each with a 4.3125 kHz bandwidth. Each sub-carrier can be independently modulated from zero to a maximum of 15 bits/sec/Hz. This allows up to 60 kbps per tone. DMT transmission allows modulation and coding techniques to be employed independently for each of the sub-channels.
The sub-channels overlap spectrally, but as a consequence of the orthogonality of the transform, if the distortion in the channel is mild relative to the bandwidth of a sub-channel, the data in each sub-channel can be demodulated with a small amount of interference from the other sub-channels. For high-speed wide-band applications, it is common to use a cyclic-prefix at the beginning, or a periodic extension at the end of each symbol, in order to maintain orthogonality, and more specifically, to eliminate inter-symbol-interference.
3. Frequency Domain Equalization
In standard DMT modulation, each N-sample encoded symbol is prefixed with a cyclic extension to allow signal recovery using the cyclic convolution property of the discrete Fourier transform (DFT). Of course, the extension may be appended to the end of the signal as well. If the length of the cyclic prefix, L, is greater than or equal to the length of the impulse response, the linear convolution of the transmitted signal with the channel becomes equivalent to circular convolution (disregarding the prefix). The frequency indexed DFT output sub-symbols are merely scaled in magnitude and rotated in phase from their respective encoded values by the circular convolution. It has been shown that if the channel impulse response is shorter than the length of the periodic extension, sub-channel isolation is achieved. Thus, the original symbols can then be recovered by transforming the received time domain signal to the frequency domain using the DFT (implemented using, e.g., the FFT), and performing equalization using a bank of single tap frequency domain equalizer (FEQ) filters. The FEQ effectively deconvolves (circularly) the signal from the transmission channel response. This normalizes the DFT coefficients allowing uniform QAM decoding.
Such an FEQ is shown in FIG. 1. The FFT calculator 20 accepts received time domain signals from line 10, and converts them to frequency domain representations of the symbols. Each frequency bin (or output) of the FFT 20 corresponds to the magnitude and phase of the carrier at the corresponding frequency. In FIG. 1, each bin therefore contains a separate symbol value X(i) for the ith carrier. The frequency domain equalizer FEQ 40 then operates on each of the FFT 20 outputs with a single-tap filter to generate the equalized symbol values Xxe2x80x2(i). The FEQ 40 inverts the residual frequency response of the effective channel by a single complex multiplication. The FEQ outputs are then decoded by a slicer, or data decision device (not shown). The FEQ taps can be updated, and can make use of the slicer output in this regard. That is, the FEQ taps may be updated so as to minimize the error between the FEQ output and the slicer output. This is commonly referred to as decision feedback equalization, or decision-directed adaptation.
4. Timing Recovery
Also shown in FIG. 1 is a clock recovery and control circuit 30. The clock recovery circuit 30 analyzes the pilot tone that is embedded in the transmitted DMT signal in ADSL communication systems.
A typical hardware solution is shown in FIG. 2. The clock recovery components are indicated with dashed lines. Control words from a clock recovery algorithm running in a DSP 10 are converted to voltage levels by a digital-to-analog converter (DAC) 12 which controls the receive sampling rate of an ADC 14 through a voltage-controlled oscillator (VCO) 16. With a pure software timing recovery solution, the DAC 12 and VCO 16 (marked in dotted line) and any associated circuitry can be eliminated. A crystal at the nominal frequency would provide the ADC 14 sample clock.
Timing information may also be recovered using software techniques. One known method of implementing software clock recovery is to digitally resample the received signal at the transmitter""s clock rate by interpolating the received samples. FIG. 3 is block diagram showing an input signal being applied to an interpolator 12, the output of which is applied to a clock recovery algorithm 22 executing on a microprocessor.
This is a general method and may be used to recover clock for any type of synchronous modulation but may differ in the way the transmit clock is extracted from the received signal. For DMT, one of the frequency bins output from a fast Fourier transform (FFT) function 30 is usually dedicated as a pilot tone. The clock recovery circuit 30, preferably an algorithm executing in a microprocessor, includes a filter to isolate the pilot tone and logic to estimate the clock offset between transmitter and receiver and to control the resampling rate in an interpolator.
The interpolation stage can be implemented a number of ways, but it generally consists of integrally interpolating receive samples to a rate (k) several times the nominal rate and then fractionally interpolating between two or more high rate samples using polynomial interpolation. Decimation to the final rate is accomplished by skipping over (not computing) samples and by computing only those samples needed to fractionally interpolate to the final rate. The interpolation rate (k) and the order of the polynomial used in the fractional interpolation can be traded off for a particular implementation in order to minimize complexity and provide tolerable interpolation error. Because this method can require tens of processor cycles for each interpolated sample it is not preferred for modems operating at high sample rates.
Because ADSL and other DMT modems are high-speed high bandwidth communication devices, they generally rely heavily on hardware solutions timing recovery solutions. As modem technologies mature, often the most important differentiator between one modem manufacture and the next is cost. One way to reduce cost is to reduce the hardware complexity of a modem. Cost savings can be significant for very high-speed modems with sample rates in the range of hundreds of kilohertz to several megahertz because of the premium placed on high-speed components. Of course, a software solution takes processor resources, which also has a cost, but processors tend to have steep development curves and newer versions are regularly introduced with increased capability and lower cost.
A software solution may also be important in applications where it is desirable (e.g., for reasons of cost, density or power dissipation) to separate the analog front-end (AFE) from the digital signal processor (DSP) running the modulation and demodulation tasks. Traditional methods of clock recovery require frequent adjustments to the sample clock of the analog-to-digital (ADC) converter located on the AFE. The rate and magnitude of these adjustments are generally controlled from a time-tracking algorithm in the DSP. A path must be provided between the DSP and AFE for clock control, and, in cases where providing a control path is difficult, a software clock recovery solution is an attractive option.
The invention has realized that it would be useful to provide a timing recovery solution for a multitone modem that can be implemented completely in software. The present invention provides a method for accomplishing this goal.
A correlator for use in a timing recovery apparatus of a receiver in a multicarrier transmission system is provided. The correlator locates the beginning of a data frame and initializes a pointer register with an address to a location within the receive signal buffer. Data is transferred to a signal converter from the receive signal buffer where the samples that are fed into the converter are determined by the address stored in the pointer register.
There are several methods of determining a symbol frame boundary in a multicarrier data signal. One such method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, forming a multiplicative estimate sequence from selected points within the difference sequence, forming a window sequence by summing selected points within the product sequence, locating the maximum value of the window sequence, and loading a pointer register based on the sequence index corresponding to the maximum value. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: Z[n]=zmaxxe2x88x92|y[n]xe2x88x92y[n+N]|, where zmax is the maximum value of |y[n]xe2x88x92y[n+N]|, and N is the number of samples in a symbol.
The step of forming a multiplicative estimate sequence, p[i,n], is performed in accordance with the relationship:             p      ⁡              [                  i          ,          n                ]              =                  ∏                  j          =          0                          Q          -          1                    ⁢              xe2x80x83            ⁢              z        ⁡                  [                      n            +            i            +                          j              ·                              (                                  N                  +                  M                  +                  P                                )                                              ]                      ,
where M+P is the length of a periodic extension, Q is the number of frames being processed, and M is the length of communication channel impulse response. The step of forming a window sequence, w[n] is formed in accordance with the relation:             w      ⁡              [        n        ]              =                  ∑                  i          =          0                                      P            ^                    -          1                    ⁢              xe2x80x83            ⁢                        ∏                      j            =            0                                Q            -            1                          ⁢                  xe2x80x83                ⁢                  z          ⁡                      [                          n              +              i              +                              j                ·                                  (                                      N                    +                    M                    +                    P                                    )                                                      ]                                ,
where 0 less than {circumflex over (P)}xe2x89xa6P.
A second alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, forming a window sequence from selected points within the difference sequence, forming a summation sequence by summing selected points within the summation sequence, locating the minimum value of the window sequence, and loading a pointer register based on the sequence index corresponding to the minimum value. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: z[n]=|y[n]xe2x88x92y[n+N]|, where N is number of symbol samples.
The step of forming a window sequence, p[j], is performed in accordance with the If relationship:             p      ⁡              [        j        ]              =                  ∑                  i          =          0                                      P            ^                    -          1                    ⁢              xe2x80x83            ⁢              z        ⁡                  [                      n            +            i            +                          j              ·                              (                                  N                  +                  M                  +                  P                                )                                              ]                      ,
where M+P is the length of a periodic extension, and M is the length of the communication channel impulse response and P is a window of nearly identical samples. The step of forming a summation sequence, w[n] is formed in accordance with the relation:             w      ⁡              [        n        ]              =                  ∑                  j          =          0                          Q          -          1                    ⁢              xe2x80x83            ⁢                        ∑                      i            =            0                                              P              ^                        -            1                          ⁢                  xe2x80x83                ⁢                  z          ⁡                      [                          n              +              i              +                              j                ·                                  (                                      N                    +                    M                    +                    P                                    )                                                      ]                                ,
where 0 less than {circumflex over (P)}xe2x89xa6P.
A third alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, forming a window sequence by weighting and summing selected points within the difference sequence, locating the minimum value of the window sequence, and loading a pointer register based on the sequence index corresponding to the minimum value. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: z[n]=|y[n]xe2x88x92y[n+N]|, where N is number of symbol samples. The window sequence is performed in accordance with the relationship:             w      ⁡              [                  n          -          R          +          1                ]              =                  ∑                  k          =          0                          R          -          1                    ⁢              xe2x80x83            ⁢                                    h            MF                    ⁡                      [                          n              -              k                        ]                          ⁢                  xe2x80x83                ⁢                  z          ⁡                      [            k            ]                                ,
where hMF is a matched filter of the channel response and R is the matched filter length.
A fourth alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, forming a window sequence by weighting and summing selected points within the difference sequence, locating the maximum value of the window sequence, and loading a pointer register based on the sequence index corresponding to the maximum value. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: z[n]=zmaxxe2x88x92|y[n]xe2x88x92y[n+N]|, where N is number of symbol samples and zmaxxe2x89xa7max{|y[n]xe2x88x92y[n+N]|}. The window sequence is performed in accordance with the relationship:             w      ⁡              [                  n          -          R          +          1                ]              =                  ∑                  k          =          0                          R          -          1                    ⁢              xe2x80x83            ⁢                                    h            MF                    ⁡                      [                          n              -              k                        ]                          ⁢                  z          ⁡                      [            k            ]                                ,
where hMF is a matched filter of the channel response and R is the matched filter length.
A fifth alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, comparing the difference sequence to a value given by xcex5 for selected points within the difference sequence, and loading a pointer register based on the minimum sequence index corresponding to the minimum value of xcex5. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: ∀m∈[0,{circumflex over (P)}xe2x88x921], |y[n+m]xe2x88x92y[n+m+N]|xe2x89xa6xcex5, where N is number of symbol samples, and xcex5 is the minimum value.
Similary, a sixth alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, comparing the difference sequence to a value given by xcex5 for selected points within the difference sequence, and loading a pointer register based on the minimum sequence index corresponding to the maximum xcex5. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship: ∀m∈[0,{circumflex over (P)}xe2x88x921], [zmaxxe2x88x92|y[n+m]xe2x88x92y[n+m+N]|]xe2x89xa7xcex5, where N is number of symbol samples, zmaxxe2x89xa7max{|y[n]xe2x88x92y[n+N]|}, and xcex5 is the maximum value.
A seventh alternative method includes the steps of forming a sample sequence from a received multicarrier signal, calculating a difference sequence from the sample sequence, locating the minimum value of the sequence, and loading a pointer register based on the sequence index corresponding to the minimum value. The sample sequence is y[n], and the step of forming the difference sequence is performed in accordance with the relationship:             z      ⁡              [        n        ]              =                  ∑                  l          =          o                                      P            ^                    -          1                    ⁢              xe2x80x83            ⁢              "LeftBracketingBar"                              y            ⁡                          [                              n                +                l                            ]                                -                      y            ⁡                          [                              n                +                N                +                l                            ]                                      "RightBracketingBar"              ,
where N is number of symbol samples.
Regarding other aspect of the invention, a digital filter is connected to the converter, and is essentially a bank of single-tap filters. One of the converter outputs corresponds to a pilot tone, and thus the digital filter provides a filtered pilot tone. The phase of the pilot is also examined to generate a pilot phase signal, preferably by examining the filter tap corresponding to the pilot. The control circuit accepts the pilot phase signal and responsively updates the pointer register if necessary. Alternatively, the control circuit updates the pointer register by deriving a phase signal directly from the relevant converter bin.
The time to frequency domain converter of the timing recovery apparatus is preferably an FFT module, but in a generalized multicarrier transmission system, the converter may apply another type of transformation such as a wavelet transform, or the like. The outputs are generally referred to as bins, where each bin corresponds to a center frequency of a subcarrier. The digital filter of the timing recovery apparatus may be implemented using a magnitude filter and a phase filter. Each of the filters are preferably a single tap filter for each subcarrier or bin. The filter taps are updated using an adaptive updating algorithm, such as a stochastic gradient algorithm, or LMS algorithm. The LMS algorithm may be first or second-order LMS.
Alternatively, the control circuit of the timing recovery apparatus processes the pilot signal directly to derive the phase information, and responsively updates the pointer register. The control circuit also provides inputs to the digital filter, which takes the form of a rotator. That is, a bank of single-tap filters that rotate the inputs. The taps are complex valued of unit magnitude, and thus have an associated phase rotation value. The control circuit updates the single-tap filters using an adaptive updating algorithm, as specified above.
The pointer register is ultimately used for timing offset compensation as disclosed herein and includes the steps of sampling a received multitone signal, converting the sampled signal to complex-valued symbols, determining the phase of an embedded pilot symbol, adjusting the phase of the complex-valued symbols in response to the determined pilot phase, and adjusting a sample pointer in response to the determined pilot phase. The step of adjusting the phase of the complex-valued symbols is preferably performed by a phase equalizer, and the step of determining the phase of an embedded pilot symbol preferably includes examining one or more filter taps within the phase equalizer. The phase equalizer is preferably an adaptive filter that utilizes the well-known adaptation techniques specified above. The step of adjusting the phase of the complex-valued symbols includes rotating the complex-valued symbols using a complex-valued, unit-magnitude, single-tap filter.
The embedded pilot symbol has an associated bin number. The step of adjusting the sample pointer includes the step of examining the pilot bin number, the total number of bins, and the pilot phase. One such method would include the steps of determining an accumulated change in the pilot phase, and comparing the accumulated change to 360 degrees times the pilot bin divided by the total number of bins. In this-manner, the receiver may determine whether the sampling offset exceeds a threshold, that is, whether the sample timing has advanced or retarded by a full sample.